Leetcode92 反转链表(反转指定位置的链表)

您所在的位置:网站首页 反转从位置 m 到 n 的链表 Leetcode92 反转链表(反转指定位置的链表)

Leetcode92 反转链表(反转指定位置的链表)

2024-07-17 17:02| 来源: 网络整理| 查看: 265

反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。 说明: 1 ≤ m ≤ n ≤ 链表长度。 示例: 输入: 1->2->3->4->5->NULL, m = 2, n = 4 输出: 1->4->3->2->5->NULL

反转链表普通做法头插法(一次遍历)

反转链表普通做法

在这里插入图片描述

定义指针 rightnode、leftnode、pre、succ、dummynode找到各个指针的位置(for循环)断链、反转、衔接 class Solution { public ListNode reverseBetween(ListNode head, int left, int right) { // 因为头节点有可能发生变化,使用虚拟头节点可以避免复杂的分类讨论 ListNode dummyNode = new ListNode(-1); dummyNode.next = head; ListNode pre = dummyNode; // 第 1 步:从虚拟头节点走 left - 1 步,来到 left 节点的前一个节点 // 建议写在 for 循环里,语义清晰 for (int i = 0; i NULL

1 -> 3 -> 2 -> 4 -> 5 -> NULL

1 -> 4 -> 3 -> 2 -> 5 -> NULL

我们可以看出来,总共需要n-m步即可,第一步是将结点3放到结点1的后面,第二步将结点4放到结点1的后面。这是很有规律的操作,那么我们就说一个就行了,比如刚开始,pre指向结点1,cur指向结点2,然后我们建立一个临时的结点t,指向结点3(注意我们用临时变量保存某个结点就是为了首先断开该结点和前面结点之间的联系,这可以当作一个规律记下来),然后我们断开结点2和结点3,将结点2的next连到结点4上,也就是 cur->next = t->next,再把结点3连到结点1的后面结点(即结点2)的前面,即 t->next = pre->next,最后再将原来的结点1和结点2的连接断开,将结点1连到结点3,即 pre->next = t。这样我们就完成了将结点3取出,加入结点1的后方。第二步将结点4取出,加入结点1的后方,也是同样的操作,



【本文地址】


今日新闻


推荐新闻


    CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3